package com.lark.algorithm.train.onChapter.linkedList;

/**
 * @author btmood
 * @version 1.0
 * @apiNote
 * Q21：合并两个有序链表
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * 示例 1：
 *
 *
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * 示例 2：
 *
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * 示例 3：
 *
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 *
 *
 * 提示：
 *
 * 两个链表的节点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * l1 和 l2 均按 非递减顺序 排列
 * @since 2024-05-20 17:12
 */
public class D20240520Q21_合并两个有序链表 {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode newHead = null;
        ListNode newEndNode = new ListNode();
        while (cur1 != null || cur2 != null) {
            if (cur1 != null && cur2 != null) {
                if (cur1.val < cur2.val) {
                    if (newHead == null) {
                        newHead = cur1;
                        newEndNode = newHead;
                    } else {
                        newEndNode.next = cur1;
                        newEndNode = newEndNode.next;
                    }
                    cur1 = cur1.next;
                } else {
                    if (newHead == null) {
                        newHead = cur2;
                        newEndNode = newHead;
                    } else {
                        newEndNode.next = cur2;
                        newEndNode = newEndNode.next;
                    }
                    cur2 = cur2.next;
                }
            } else if (cur1 != null) {
                if (newHead == null) {
                    newHead = cur1;
                    newEndNode = newHead;
                } else {
                    newEndNode.next = cur1;
                    newEndNode = newEndNode.next;
                }
                cur1 = cur1.next;
            } else if (cur2 != null) {
                if (newHead == null) {
                    newHead = cur2;
                    newEndNode = newHead;
                } else {
                    newEndNode.next = cur2;
                    newEndNode = newEndNode.next;
                }
                cur2 = cur2.next;
            }
        }
        return newHead;
    }

    public ListNode mergeTwoLists3(ListNode list1, ListNode list2) {
        ListNode dummyHead = new ListNode();
        ListNode endNode = dummyHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                endNode.next = list1;
                list1 = list1.next;
            } else {
                endNode.next = list2;
                list2 = list2.next;
            }
            // 这一步遗漏了！
            endNode = endNode.next;
        }
        endNode.next = null == list1 ? list2 : list1;
        return dummyHead.next;
    }

    // 按照升序合并list1和list2
    // 返回新链表的头节点
    public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        // list1 != null && list2 != null
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists2(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists2(list1, list2.next);
            return list2;
        }
    }


    public static class  ListNode {
        int val;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        ListNode next;

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            ListNode cur = next;
            sb.append(val);
            while (cur != null) {
                sb.append("=>");
                sb.append(cur.val);
                cur = cur.next;
            }
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        D20240520Q21_合并两个有序链表 m = new D20240520Q21_合并两个有序链表();
        D20240520Q21_合并两个有序链表.ListNode l1 = new D20240520Q21_合并两个有序链表.ListNode(4, null);
        D20240520Q21_合并两个有序链表.ListNode l2 = new D20240520Q21_合并两个有序链表.ListNode(2, l1);
        D20240520Q21_合并两个有序链表.ListNode l3 = new D20240520Q21_合并两个有序链表.ListNode(1, l2);

        D20240520Q21_合并两个有序链表.ListNode l11 = new D20240520Q21_合并两个有序链表.ListNode(4, null);
        D20240520Q21_合并两个有序链表.ListNode l12 = new D20240520Q21_合并两个有序链表.ListNode(3, l11);
        D20240520Q21_合并两个有序链表.ListNode l13 = new D20240520Q21_合并两个有序链表.ListNode(1, l12);

        D20240520Q21_合并两个有序链表.ListNode listNode = m.mergeTwoLists(l3, l13);
        System.out.println(listNode);
    }
}
